МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра автоматизованих систем управління Розрахункова робота Тема: «Робота з розрідженими масивами за допомогою масиву вказівників»  Львів 2011 ВСТУП ПРОЕКТУВАННЯ РОЗРІДЖЕНИХ МАСИВІВ Розглянуто питання створення структурованого типу даних – розріджених масивів (sparse arrays) для здійснення ефективної роботи з матрицями великих розмірів,у яких значна кількість елементів не використовується. Здатність розріджених масивів оптимізувати доступ до таких даних робить їх надзвичайно корисними в багатьох задачах, які виникають під час розроблення сучасних програмних продуктів. До таких задач належить робота з топологічними матрицями, які використовуються для відображення зв'язків елементів у електронних схемах, що асоціюються з її клітинами. Завдяки використанню розріджених масивів пам'ять для зберігання кожної з таких клітин виділяється з пули вільної пам'яті тільки в міру потреби. Той факт, що пам'ять для масиву виділяється при його створенні, означає, що розмір найбільшого масиву, який ви зможете описати у своїй програмі, обмежений (зокрема) обсягом доступної пам'яті. Якщо вам знадобиться масив більшого розміру, ніж дозволяють можливості комп'ютера, доведеться реалізовувати його якимось іншим чином. Навіть якщо великий масив розміститься в пам'яті, створення його може істотно зменшити доступні ресурси системи, оскільки пам'ять, зайнята великим масивом, виявляється недоступною для іншої частини програми та інших процесів, що працюють в системі. А це в свою чергу може негативно позначитися на загальній продуктивності програми або комп'ютера в цілому. У тих ситуаціях, коли будуть використовуватися не всі елементи масиву, виділення пам'яті під весь масив представляється особливо марнотратною тратою системних ресурсів. Щоб позбутися від проблем, викликаних потребою в пам'яті для великих рідко заповнених масивів, були придумані деякі прийоми роботи з розрідженими масивами. Всі вони характеризуються однією спільною рисою: пам'ять для елементів масиву виділяється тільки при необхідності. ОГЛЯД ЛІТЕРАТУРИ Під час виконання різних інженерних розрахунків часто доводиться мати справу з так званими розрідженими масивами, значна кількість елемен- тів яких фактично не використовується. У середовищі фахівців, робота яких пов'язана з дослідженням розріджених масивів, у обігу широко вживають два терміни: логічний і фізичний масиви. Логічний масив є уявним, фігурує тільки у математичних записах і графічних представленнях, а фізичний – фактично існує тільки в програмі. Наприклад, якщо певна електронна схема описується топологічною матрицею (суміжності чи інциденцій) розміром 100×5000 елементів, то логічний масив складатиметься з такої ж самої кількості елементів навіть у тому разі, якщо цей масив у програмі фізично не існує. Якщо у цій матриці фактично використовуються тільки 100 елементів, то саме вони і займатимуть фізичну пам'ять комп'ютера. Поодинокі елементи чи навіть структури (записи), які зберігаються у звичайному масиві (чий індекс є аналогом ключа), можуть бути знайдені дуже швидко і без будь-яких порівнянь. Якщо відомо ключ (тобто індекс масиву), розмір запису і початкову адресуа масиву, то адресу потрібного запису обчислюємо за допомогою множення і додавання. Зазвичай, це питання стає цікавим тільки тоді, коли нам потрібно зберігати значну кількість записів. Нехай, замість 100 елементів у нас є 5 000, а розмір топологічної матриці залишається попереднім. Наш гіпотетичний масив, який складається з такої кількості елементів, все ще на 99 % порожній, тобто ми тепер не можемо знехтувати проблемою пошуку потрібного запису серед їх півмільйонної кількості. Структурований тип даних, який має назву розріджений масив, якраз і призначений для вирішення таких неоднозначних ситуацій шляхом ефективного пошуку відповідних об'єктів. Розгляд основних особливостей проектування одно- і двовимірних розріджених масивів для роботи з матрицями, бі...